#include <vector>
#include <string>

using namespace std;

class Solution
{
public:
    bool col[20], dg[20], ndg[20];
    vector<vector<string>> solveNQueens(int n)
    {
        for (int i = 0; i < 20; ++i)
        {
            col[i] = dg[i] = ndg[i] = false;
        }

        vector<vector<string>> ret;
        vector<string> tmp;
        tmp.reserve(n);
        string road;
        road.reserve(n);
        bfs(ret, tmp, road, n);
        return ret;
    }

    void bfs(vector<vector<string>> &ret, vector<string> &tmp, int n)
    {
        if (n == tmp.size())
        {
            ret.push_back(tmp);
        }
    }
};